#include<iostream>
#include<cmath>
using namespace std;
const int N=1e5+1e4;
struct node{
	int now;
	int key;
	int next;
};
node p[N],de[N],an[N];
int l1,l2;
int st,n;
int vis[N];
int main()
{
	cin>>st>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		p[x].key=y;
		p[x].next=z;
	}
	for(int i=1;i<=n;i++)
	{
		int k=abs(p[st].key);
// 		cout<<k<<endl; 
		if(!vis[k])
		{
			an[l1].now=st;
			an[l1++].key=p[st].key;
			vis[k]=1;
		}
		else
		{
			de[l2].now=st;
			de[l2++].key=p[st].key;
		}
		st=p[st].next; 
        if(st==-1)
        break;
	}
	for(int i=0;i<l1;i++)
	{
		if(l1-1!=i) 
		printf("%05d %d %05d\n",an[i].now,an[i].key,an[i+1].now);
		else
        printf("%05d %d %d\n",an[l1-1].now,an[l1-1].key,-1);
	}
	for(int i=0;i<l2;i++)
	{
		if(l2-1!=i) 
		printf("%05d %d %05d\n",de[i].now,de[i].key,de[i+1].now);
		else
        printf("%05d %d %d\n",de[l2-1].now,de[l2-1].key,-1);
	}
	return 0;
} 
